package com.kevinkk.backtracking;

/**
 * 编写一个程序，通过填充空格来解决数独问题。
 */
public class SudokuSolver {
    class Solution {
        public void solveSudoku(char[][] board) {
            backtracking(board);
        }

        private boolean backtracking(char[][] board) {
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board.length; j++) {
                    if (board[i][j] == '.') {
                        for (int k = 1; k < 10; k++) {
                            if (check(board, i, j, k)) {
                                board[i][j] = (char) ('0' + k);
                                if (backtracking(board))
                                    return true;
                                board[i][j] = '.';
                            }
                        }
                        return false;
                    }
                }
            }

            return true;
        }

        private boolean check(char[][] board, int row, int col, int k) {
            char value = (char) ('0' + k);
            // 行
            for (int i = 0; i < board.length; i++)
                if (board[row][i] == value) return false;
            // 列
            for (int i = 0; i < board.length; i++)
                if (board[i][col] == value) return false;
            // 宫
            for (int i = row / 3 * 3, countI = 0; countI < 3; countI++) {
                for (int j = col / 3 * 3, countJ = 0; countJ < 3; countJ++) {
                    if (board[i + countI][j + countJ] == value)
                        return false;
                }
            }

            return true;
        }
    }
}
